package com.jxb.seven;

/**
 * 解码方法???
 *
 * @author jiaobo
 * @date Created in 2025/1/5 15:10
 **/
public class DecodeWays_91 {

    /*标准DP实现*/
    //eg:1234
    //i = 2:dp[i-2]=1 dp[i]=2
    //dp[2]:3 12,1 23,2 13---》三种
    //dp[1]:2 2 1,12---》2种
    //dp[0]:1---》1种
    //所以确定状态转移公式：dp[i] = dp[i] + dp[i-2]
    //因为组成的数字在10~26之间，所以当前位置和前一个位置可以进行组合，dp[i] = dp[i-2]
    //dp[i]表示截止目前位置的字符串拥有多少种解码方式，
    //---------代码逻辑步骤
    //eg:1234--->dp[] = [1,1,2,3];dp[i]=2
    //
    //1：单独解码原始字符串
    //2：i>=2，与前面字符进行组合
    //  dp[i] = dp[i] + dp[i-2]
    public static int numDecodings2(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        //初始化
        dp[0] = 1;
        //填充dp数组
        for (int i = 1;i<=n;i++) {
            //单独解码原始字符串
            if (s.charAt(i-1) != '0') {
                dp[i] = dp[i-1];
            }
            if (i>=2) {
                int num = (s.charAt(i-2) - '0') * 10 + s.charAt(i-1) - '0';
                if (num >= 10 && num <= 26) {
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[n];
    }

    /*DP+滚动数组实现*/
    public int numDecodings(String s) {
        int n = s.length();
        int prePre = 0,pre = 1,curr = 0;
        for (int i = 1;i<=n;++i) {
            curr = 0;
            //当前字符单独映射
            if (s.charAt(i-1) != '0') {
                curr += pre;
            }
            if (i>=2) {
                int num = (s.charAt(i-2) - '0') * 10 + s.charAt(i-1) - '0';
                if (num >= 10 && num <= 26) {
                    curr += prePre;
                }
            }
            prePre = pre;
            pre = curr;
        }
        return curr;
    }

}
